package com.zhouhong.muke_leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-05 13:08
 **/
//给定一个二叉树，返回它的 后序 遍历。
//
// 示例:
//
// 输入: [1,null,2,3]
//   1
//    \
//     2
//    /
//   3
//
//输出: [3,2,1]

public class LeetCode0145 {

    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                result.addFirst(cur.val);
                cur = cur.right;
            }else {
                cur = stack.pop();
                cur = cur.left;
            }
        }
        return result;
    }


}
